#include "QuadraticTDP.h"

#include <thread>
#include <algorithm>

#include "liberty/Liberty.hh"
#include "tool_api/ista_io/ista_io.h"
#include "api/TimingEngine.hh"
#include "api/TimingIDBAdapter.hh"

namespace ieda_contest {

// #define Cw 0.16e-15
// #define Rw 2.535
// #define DEBUG

// init
QuadraticTDP::QuadraticTDP( ContestDB* database) {
  this->_contest_database = database;
  vector<double> critical_vec;
  for (auto pin : _contest_database->get_ContestPin_pvec()) {
    bool flipflop_input_flag = false;
    bool flipflop_output_flag = false;
    auto inst = pin->get_ContestInstance();
    if (inst && inst->isFlipflop()) {
      if (isFlipflopDataInput(pin)) {
        flipflop_input_flag = true;
      }
      if (pin->isInstanceOutputPin()) {
        flipflop_output_flag = true;
      }
    }
    if (pin->isPO() || flipflop_input_flag) {
      _timing_endpoints.emplace(pin);
    }
    if (pin->isPI() || pin->isClockPin() || flipflop_output_flag) {
      _timing_startpoints.emplace(pin);
    }
  }

  //calculate wns 
    for (auto pin : _timing_endpoints) {
    if (pin->get_late_slack() < wns) {
      wns = pin->get_late_slack();
    }
  }
  
  //calculate medianCriticality
    for (auto pin : _contest_database->get_ContestPin_pvec()) {
        critical_vec.push_back(getPinCriticality(pin));
        pin2slack_map[pin] = pin->get_late_slack();
  }

  std::sort(critical_vec.begin(), critical_vec.end());
  medianCriticality = critical_vec[critical_vec.size() / 2];


/////debug
// vector<double> slack;
//  for(auto cell : _contest_database->get_ContestInstance_pvec())
//  {
//     slack.push_back(getCellWorstSlack1(cell));
//  }

}

// run top level op
void QuadraticTDP::runQuadraticTDPOpt()
{
  LOG_INFO << "-----------------------------QuadraticTDPOpt is started ! ! !-------------------------------";
  int max_endpoint_nums = 3;
  _most_critical_endpoints.reserve(max_endpoint_nums);
  obtainTopCriticalEndpoints(_most_critical_endpoints, max_endpoint_nums);

  for (auto instance : _contest_database->get_ContestInstance_pvec()) {
    mapCellToIndex[instance] = -1;
  }
  defaultFlow();
  LOG_INFO << "---------------------------QuadraticTDPOpt is finished ! ! !---------------------------------";
}

// quadratic TDP flow.
void QuadraticTDP::defaultFlow()
{
  int max_iter = 1;  // 可以调成2 或者 3试试

  // "QP-Step1"：1.runPathStraightening   2.cell balancing
  while (max_iter--) {
    // updateTopologyManager();
    _contest_database->get_timing_engine()->updateTiming();
    runPathStraighteningFlow();  // pass
  };

    _contest_database->get_timing_engine()->updateTiming();
}

// ispd16 methods

void QuadraticTDP::runCellFix()
{
  LOG_INFO << "----------------------- CellFix is started ! ! ! ------------------------------";
  
  _contest_database->get_timing_engine()->updateTiming(); 

  int iter = 1;
  while (iter--) {
    std::deque<std::tuple<float, ContestInstance*>> cells;                      // number是float
    for (auto cell : _contest_database->get_ContestInstance_pvec()) {               // 处理所有cells
      const double criticalityLate = getCellCriticality(cell, Mode::LATE);  // 这里的关键度就是 slack/wns。
      // std::cout << " criticalityLate :" << criticalityLate << std::endl;

      //要处理的criticality > 0.7 的cell，具体例子具体调！
      if ((std::abs(criticalityLate) >= 0.7)) {
        // const double criticalityEarly = getCellCriticality(cell, Mode::ERALY);
        if (!cell->isFixed() && !cell->isFlipflop() && !cell->isMacro() && !cell->isBuffer())
          cells.push_back(std::make_tuple(criticalityLate, cell));
        // end if0
      }  // end if
    }    // end for

    // Sort buffer by criticality.
    std::sort(cells.begin(), cells.end());

    // Equalize buffers.
    int movedCells = 0;
    int failed = 0;

    const int numCells = cells.size();


    // for(int i = 0; i < numCells; i++){
    //   auto cell = std::get<1>(cells[i]);
    //   std::cout<<"cell slack: "<< getCellWorstSlack(cell)<<std::endl;
    // }

    for (int i = numCells - 1; i >= 0; i--) {
      auto cell = std::get<1>(cells[i]);  // 先是从cell中取到第i个元素，再从这个元素中取第2个元素。

      if (!doCellBalancing(cell)) {
        failed++;
      }  // end if
      else {
        movedCells++;
      }

    }  // end for

  // _contest_database->get_timing_engine()->updateTiming(); 


    LOG_INFO << "*******************************";
    LOG_INFO << "Need fix cell nums :" << cells.size();
    LOG_INFO << "Cell balancing failed nums :" << failed;
    LOG_INFO << "Cell balancing succeed nums :" << movedCells;
    LOG_INFO << "*******************************";
  }  // end while


  
  // _contest_database->get_timing_engine()->updateTiming(); 
  LOG_INFO << "----------------------- CellFix is finished ! ! ! ------------------------------";
}

// quadratic methods

void QuadraticTDP::runPathStraighteningFlow()
{
  markAsMovableAllNonFixedCells(false);  // 将所有非固定单元标记为可移动的

  buildMapping();  // cell与id的map

  // updateCentrality();

  copyCellsLocationFromSessionToLinearSystem();  // 把session中的cell复制到线性系统中。

  buildLinearSystem(false);  // 建立线性系统

  neutralizeSystemWithSpreadingForces();  // 中和系统

  generateStraighteningForces(false);  // 对关键路径加线加权

  solveLinearSystem(false);  // 这个要开启false的时候可以优化

  copyCellsLocationFromLinearSystemToSession();  // 把线性系统中的cell位置复制回session。
}

void QuadraticTDP::markAsMovableAllNonFixedCells(const bool considerCriticalCellsAsFixed)
{
  needFixMovableCells.clear();
  for (auto* instance : _contest_database->get_ContestInstance_pvec()) {
    if (canBeSetAsMovable(instance, considerCriticalCellsAsFixed)) {
      needFixMovableCells.push_back(instance);
    }  // end if
  }    // end for
}

void QuadraticTDP::buildMapping()
{
  mapIndexToCell.clear();

  mapIndexToCell.resize(needFixMovableCells.size());

  int index = 0;
  for (ContestInstance* cell : needFixMovableCells) {
    mapCellToIndex[cell] = index;
    mapIndexToCell[index] = cell;
    index++;
  }  // end for
}

void QuadraticTDP::copyCellsLocationFromSessionToLinearSystem()  // 把session中的cell复制到线性系统中。
{
  const int numMovableElements = needFixMovableCells.size();

  px.clear();
  py.clear();
  px.assign(numMovableElements, 0);  // 设置vector大小为numMovableElements，元素值全为0。
  py.assign(numMovableElements, 0);

  for (auto cell : _contest_database->get_ContestInstance_pvec()) {
    const int index = mapCellToIndex[cell];
    if (index < 0)
      continue;
    const Point<int32_t> cellPos = cell->get_center_coord();
    px[index] = cellPos.get_x();
    py[index] = cellPos.get_y();
  }  // end for
}

void QuadraticTDP::buildLinearSystem(const bool stress)  // 建立线性系统
{
  bx.clear();
  by.clear();
  bx.assign(mapIndexToCell.size(), 0);
  by.assign(mapIndexToCell.size(), 0);

  // Clear anchors
  removeAnchors();

  std::set<ContestNet*> nset;  // 使用set可以高效的进行查找和插入！！！它是一个有序的集合，这里是为了提高查找效率

  // 把单元相关的所有net都存入net中，但是忽略buffer 和clock net
  for (auto instance : _contest_database->get_ContestInstance_pvec()) {
    if (mapCellToIndex[instance] < 0)
      continue;
    for (auto pin : instance->get_pin_vec()) {
      auto net = pin->get_ContestNet();
      if (net) {
        if (net->isClockNet())
          continue;

        auto driver = net->get_driver_pin();
        if(!driver) continue;
        ContestInstance* instance = driver->get_ContestInstance();
        if(!instance) continue;
        if (driver && instance->isBuffer())
          continue;
        nset.insert(net);  // 接收所有非clocknet以及buffer所连接的net。
      }                    // end if
    }                      // end for
  }                        // end for

  // 遍历所有要处理的net
  for (ContestNet* net : nset) {
    ContestPin* driver = net->get_driver_pin();

    double R = 1;

    if (_enableRC) {
      double cell_max_resistance = 0;
      for (auto pin : driver->get_ContestInstance()->get_pin_vec()) {
        cell_max_resistance = std::max(getPinResistance(pin), cell_max_resistance);
      }
      R = 0.1 * cell_max_resistance;  // loadCapacitance;
    }

    R = std::max(R, minimumResistance);  // _enableRC = false 时，R = 1;

    // 处理net的不同的pin之间
    for (auto pin0 : net->get_pins()) {
      ContestInstance* cell0 = pin0->get_ContestInstance();
      const int index0 = mapCellToIndex[cell0];

      if (index0 == -1)
        continue;

      for (auto pin1 : net->get_pins()) {
        if (pin0 == pin1)
          continue;

        ContestInstance* cell1 = pin1->get_ContestInstance();
        const int index1 = mapCellToIndex[cell1];

        if ((index0 != -1 && index1 != -1) && index0 >= index1)
          continue;

        double weight = R * double(1) / std::max(1, static_cast<int>((net->get_pins().size() - 1)));
        // double weight = R;

        if (stress) {
          // 待办
          weight *= 1 + getNetCriticality(net);
        }  // end if

        if (index0 != -1 && index1 != -1) {
        // add movable-to-movable connection
          // dscp待办
          dscp.AddElement(index0, index1, -weight);  // 第一个参数表示行，第二个参数表示列，如果该位置有值了，则会叠加。
          dscp.AddElement(index1, index0, -weight);
          dscp.AddDiagonalElement(index0, weight);
          dscp.AddDiagonalElement(index1, weight);
        } else if (index0 != -1) {
          // add movable-to-fixed connection
          const Point<int32_t> pos1 = pin1->get_center_coord();
          bx[index0] += weight * pos1.get_x();
          by[index0] += weight * pos1.get_y();

          dscp.AddDiagonalElement(index0, weight);
        } else if (index1 != -1) {
          // add fixed-to-movable connection
          const Point<int32_t> pos0 = pin0->get_center_coord();
          bx[index1] += weight * pos0.get_x();
          by[index1] += weight * pos0.get_y();

          dscp.AddDiagonalElement(index1, weight);
        }  // end if
      }    // end for
    }      // end for
  }        // end for

  a.Reset();

#ifdef DEBUG
  a.Initialize(dscp, true);
#else
  a.Initialize(dscp, false);
#endif
  dscp.Clear();
}

void QuadraticTDP::neutralizeSystemWithSpreadingForces()  // 中和系统
{
  for (int i = 0; i < a.GetDimension(); i++)
    a.AddDiagonalElement(i, .1);

  std::vector<double> nx(px.size(), 0.0);
  std::vector<double> ny(py.size(), 0.0);

  ieda_contest::Mul(a, px, nx);  // 向量a与px的乘积结果存到nx中，：：表示全局作用域。
  ieda_contest::Mul(a, py, ny);

  std::vector<double> fx(px.size(), 0.0);
  std::vector<double> fy(py.size(), 0.0);

  ieda_contest::Sub(nx, bx, fx);
  ieda_contest::Sub(ny, by, fy);

  ieda_contest::Add(fx, bx, bx);
  ieda_contest::Add(fy, by, by);
}

void QuadraticTDP::generateStraighteningForces(const bool stress)  // 对关键路径加线加权
{
  fx.clear();
  fy.clear();
  fw.clear();
  fx.assign(mapIndexToCell.size(), 0.0);
  fy.assign(mapIndexToCell.size(), 0.0);
  fw.assign(mapIndexToCell.size(), 0.0);

  const double initAlpha = getSmoothedCriticality(_most_critical_endpoints.front());

  const double alpha = 0;
  const double beta = 1.0;
  for (ContestNet* net : _contest_database->get_ContestNet_pvec()) {
    auto driver = net->get_driver_pin();

    if (!driver) {
      continue;
      LOG_WARNING << "Net without a driver.\n ";
    }
    auto driverCell = driver->get_ContestInstance();
    if(!driverCell) continue; 
    const double driverCriticality = getSmoothedCriticality(driver);
    if (driverCriticality > beta)
      continue;

    if (driverCriticality < alpha)
      continue;

    const bool driverIsMovable = canBeSetAsMovable(driverCell, false);

    bool enableRC = true;
    double R = 1;

    if (enableRC) {
      double driverResistance = 0;
      for (auto pin : driverCell->get_pin_vec()) {
        driverResistance = std::max(driverResistance, getPinResistance(pin));
      }
      R = 0.1 * driverResistance;  // e * loadCapacitance;
    }                              // end if

    R = std::max(R, 0.01);
    for (ContestPin* pin : net->get_sink_pins()) {
      const double pinCriticality = getSmoothedCriticality(pin);
      // const double pinCentrality = getPinCentrality(pin);

      if (pinCriticality < alpha || approximatelyEqual(pinCriticality, alpha))
        continue;

      if (pinCriticality > beta)
        continue;

      double weight =  // 10 * R;
          // 5 * R * (1 + pinCriticality);
      10 * R * ( 1 + 0.5 * pinCriticality );
      // R * ( 1 + 3 * pinCentrality + 6 * pinCriticality );
      // R * ( 1 + 0.2 * std::exp( std::pow( pinCentrality, 3) - 1 ) );
      // R * ( 0.7 + 0.3 * pinCentrality );
      // R * ( 0.3 * pinCentrality + 0.7 * pinCriticality );

      if (stress)
        weight *= R;

      ContestInstance* cell = pin->get_ContestInstance();

      if (!cell) {
        LOG_WARNING << "Pin without a cell.\n";
        continue;
      }  // end if

      const bool cellIsMovable = canBeSetAsMovable(cell, false);

      if (driverIsMovable && !cellIsMovable) {
        const int index = mapCellToIndex[driverCell];
        // const PhysicalCell pCell = session.getPhysicalCell( cell );
        // const PhysicalPin pPin = session.getPhysicalPin( pin );
        const Point<int32_t> pinPos = pin->get_center_coord();

        fw[index] += weight;
        // fx[ index ] += weight * ( pCell.lower().x + pPin.dx );
        // fy[ index ] += weight * ( pCell.lower().y + pPin.dy );
        fx[index] += weight * (pinPos.get_x());
        fy[index] += weight * (pinPos.get_y());

        continue;

      } else if (!driverIsMovable && cellIsMovable) {
        const int index = mapCellToIndex[cell];
        // const PhysicalCell pCell = session.getPhysicalCell( driverCell );
        // const PhysicalPin pPin = session.getPhysicalPin( design.getDriver( net ) );
        const Point<int32_t> pinPos = net->get_driver_pin()->get_center_coord();

        fw[index] += weight;
        // fx[ index ] += weight * ( pCell.lower().x + pPin.dx );
        // fy[ index ] += weight * ( pCell.lower().y + pPin.dy );
        fx[index] += weight * (pinPos.get_x());
        fy[index] += weight * (pinPos.get_y());
        continue;
      } else if (!driverIsMovable && !cellIsMovable)
        continue;

      const int index1 = mapCellToIndex[driverCell];
      const int index2 = mapCellToIndex[cell];

      // 用于捕获异常
      try {
        a.AddElement(std::max(index1, index2), std::min(index1, index2), -weight);
        a.AddElement(std::min(index1, index2), std::max(index1, index2), -weight);
      } catch (std::exception& e) {
        std::cout << "Exception at line: " << __LINE__ << std::endl;
      }  // end try-catch

      a.AddDiagonalElement(index1, weight);
      a.AddDiagonalElement(index2, weight);
    }  // end for
  }
}

// 待办
void QuadraticTDP::solveLinearSystem(bool spreadingForces)  // 再次求解线性系统
{
  // Creates local variables for the system...
  SquareCompressedRowMatrix& a = this->a; 
  std::vector<double>& bx = this->bx;
  std::vector<double>& by = this->by;

  // Add spreading forces to the system if enabled...
  if (spreadingForces) {
    for (long unsigned int i = 0; i < bx.size(); i++) {
      a.AddDiagonalElement(i, fw[i]);
      bx[i] += fx[i];
      by[i] += fy[i];
    }  // end for
  }    // end if

  // Solves linear system...
  std::thread tx([&]() {
    ieda_contest::SolveByConjugateGradientWithDiagonalPreConditioner(a, bx, px, 1000);
  });  // lamda函数用的是局部变量的引用。会改变其值。且lamda函数会直接被调用，不需要声明。

  std::thread ty([&]() { 
    ieda_contest::SolveByConjugateGradientWithDiagonalPreConditioner(a, by, py, 1000); });

  //有问题，求解时迭代次数为0

  // 等待线程完成。不然会与在这两个线程没完成时执行主线程！
  tx.join();  // 此处是等待tx线程完成！
  ty.join();  // 此处是等待ty线程完成！
}

void QuadraticTDP::copyCellsLocationFromLinearSystemToSession()
{
  // std::vector<ContestPin*> path;
  // ContestPin* most_critical_pin = nullptr;

  // for (auto pin : _timing_endpoints) {
  //   if (pin->get_late_slack() < wns) {
  //     wns = pin->get_late_slack();
  //     most_critical_pin = pin;
  //   }
  // }
  // obtainOnePathPin(most_critical_pin, path);
  // const double pathLengthBefore = computePathManhattanLength(path);

  const bool moveTentatively = false;

  // double minDisplacement = 4 * _contest_database->get_ContestLayout()->get_row_height();

  double minDisplacement = 1e-6f;

  LOG_INFO << "[Quadratic Placement] minDisplacement = " << minDisplacement << "\n";

  initialPositions.resize(mapIndexToCell.size());
  for (size_t i = 0; i < mapIndexToCell.size(); ++i) {
    initialPositions[i].set_x(std::numeric_limits<double>::quiet_NaN());
    initialPositions[i].set_y(std::numeric_limits<double>::quiet_NaN());
  }

  std::vector<std::tuple<double, ContestInstance*, int>> orderedCells;  // 第一个存放cell的slack，第三个存放cell的id
  for (auto cell : _contest_database->get_ContestInstance_pvec()) {
    const int index = mapCellToIndex[cell];  // 拷贝赋值

    if (index < 0)  // index < 0表示固定的cell
      continue;

    const double slack = getCellWorstSlack(cell);
    // 通过求解线性系统得到的位置解。
    const double x = px[index];
    const double y = py[index];
    const Point<double> newPos(x, y);  // 常量对象！成员变量不能修改，以及所有成员函数可以调用，但是成员函数都被编译成常量函数。
    const Point<double> oldPos(cell->get_center_coord().get_x(), cell->get_center_coord().get_y());

    double displacement = std::sqrt((newPos.get_x() - oldPos.get_x()) * (newPos.get_x() - oldPos.get_x())
                                    + (newPos.get_y() - oldPos.get_y()) * (newPos.get_y() - oldPos.get_y()));
  LOG_INFO << "[Quadratic Placement] Displacement = " << displacement << "\n";
    // 如果移动的距离小于了minDisplacement，就不copy回去！！
    if (_enableMinDisplacement) {
      if (displacement < minDisplacement) {
        continue;
      }  // enf if
    }
    orderedCells.push_back(std::make_tuple(slack, cell, index));
  }

  std::sort(orderedCells.begin(), orderedCells.end());

  double averageDisplacement = 0.0;
  int numMoved = 0;
  int success_nums = 0;
  for (const std::tuple<float, ContestInstance*, int>& e : orderedCells) {
    auto cell = std::get<1>(e);
    const int index = std::get<2>(e);
    const double x = px[index];
    const double y = py[index];
    const Point<double> newPos(x, y);
    const Point<double> oldPos(cell->get_center_coord().get_x(), cell->get_center_coord().get_y());

    initialPositions[index].set_x(oldPos.get_x());
    initialPositions[index].set_y(oldPos.get_y());

    if (moveTentatively) {
      //  moveCellTowards(cell, newPos.convertToDbu(), 0.1);
    } else {
      if (!moveCell(cell, newPos.get_x(), newPos.get_y())) {
          std::cout << "[WARNING]: move error at " << __FILE__ << ": " << __LINE__ << "\n";
      }else{
        success_nums++;  // end if
      }
    }                  // end if
    numMoved++;

  }  // end for

  averageDisplacement /= numMoved;
  // averageDisplacement /= session.getRows()[0].height();
  averageDisplacement /= (double) _contest_database->get_ContestLayout()->get_row_height();
  std::cout << " Need Move Cell Nums : " << orderedCells.size() << std::endl;
  std::cout << "Succed move cell nums :" << success_nums << std::endl;
  std::cout << "Fail move cell nums :" << orderedCells.size() - success_nums << std::endl;

  // const double pathLengthAfter = computePathManhattanLength(path);
  // if (averageDisplacement) {
  //   std::cout << "**** Path " << path.front()->get_name();
  //   std::cout << " -> " << path.back()->get_name() << " ****\n";
  //   std::cout << "+------------+------------+----------+" << std::endl;
  //   std::cout << " Length before: " << pathLengthBefore << "\n";
  //   std::cout << " Length now: " << pathLengthAfter << "\n";
  //   std::cout << " Change (%): ";
  //   std::cout << std::fixed;
  //   std::cout << std::showpos << 100 * ((pathLengthBefore - pathLengthAfter) / pathLengthBefore) << "\n";
  //   std::cout << "+------------+------------+----------+" << std::endl;
    // end if
}  // end if


bool QuadraticTDP::doCellBalancing(ContestInstance* cell)
{
  const Point<int32_t> oldPos = cell->get_center_coord();
  if (cell->isFixed()) {
    return false;  // don't move fixed cells
  }                // end if

  double avgPx = 0;
  double avgPy = 0;
  double avgPx_1 = 0;
  double avgPy_1 = 0;
  double totalWeight = 0;
  int numPos = 0;
  double new_pos_x = 0;

  for (auto opin : cell->get_outpin_vec()) {
    auto onet = opin->get_ContestNet();

    for (auto ipin : cell->get_inpin_vec()) {
      auto inet = ipin->get_ContestNet();
      if (!inet)
        continue;

      auto driver = inet->get_driver_pin();
      if (!driver)
        continue;

      if (driver->isPI() || driver->isPO() || driver->isPIO()) {
        continue;  // [TODO] Skip for now, in the future use input driver if available...
      }            // end if

      const double R0 = getPinResistance(ipin);
      const double R1 = getPinResistance(driver);

      for (auto sink : onet->get_sink_pins()) {
        const double C1 = getPinCap(ipin);
        const double C2 = getPinCap(sink);

        const Point<int32_t> driverPos = driver->get_center_coord();
        const Point<int32_t> ipinPos = ipin->get_center_coord();
        const Point<int32_t> opinPos = opin->get_center_coord();
        const Point<int32_t> sinkPos = sink->get_center_coord();

        const double d = computeManhattanDistance(driverPos, sinkPos);
        const double a = 0;

        if (d < 1e-6) {
          continue;
        }  // end if



         double w0 = getPinCriticality(driver);
         double w1 = getPinCriticality(sink);
        if(w0 > 1.0){
          w0 = 1.0;
        }
        if(w1 > 1.0){
          w1 = 1.0;
        }

        // const double w0 = getPinImportance(driver);
        // const double w1 = getPinImportance(sink);

        if ((w0 + w1) < 1e-6)
          continue;
      int distance = 1;
      int unit = dmInst->get_idb_builder()->get_def_service()->get_design()->get_units()->get_micron_dbu();
      std::optional<double> width = std::nullopt;
      double Cw = dynamic_cast<ista::TimingIDBAdapter*>(_contest_database->get_timing_engine()->get_db_adapter())->getCapacitance(3, distance / 1.0 / unit, width);
      double Rw = dynamic_cast<ista::TimingIDBAdapter*>(_contest_database->get_timing_engine()->get_db_adapter())->getResistance(3, distance / 1.0 / unit, width);
          //Cw和Rw的取值要拿到。
        const double actualD
            = (Cw * w1 * R1 - Cw * w0 * R0 + Rw * w1 * C2 - Rw * w0 * C1 + (Cw * d - a * Cw) * Rw * w1) /
										   (Cw * Rw * w1 + Cw * Rw * w0);

        const double d0 = std::min(d - a, std::max(0.0, actualD));
        new_pos_x   = d0;
        const double dx = sinkPos.get_x() - driverPos.get_x();
        const double dy = sinkPos.get_y() - driverPos.get_y();
        const double scaling = d0 / d;

        const double weight = w0 + w1;

        avgPx += weight * (scaling * dx + driverPos.get_x());
        avgPy += weight * (scaling * dy + driverPos.get_y());

        avgPx_1 +=  scaling * dx + driverPos.get_x();
        avgPy_1 +=  scaling * dy + driverPos.get_y();

        totalWeight += weight;
        numPos++;
      }
    }
  }
  bool success = false;

  if (numPos > 0 && totalWeight > 0) {
    avgPx /= totalWeight;
    avgPy /= totalWeight;
    if (!moveCell(cell, avgPx, avgPy)) {
        std::cout << "[WARNING]: move error at " << __FILE__ << ": " << __LINE__ << "\n";
    }else{
    success = true;   // moveCell(cell, avgPx, avgPy);
    }               // end if
    // double oldCost;
    // double newCost;
    // CostType costFunction = COST_LOCAL_DELAY;
    // success = moveCellWithCostEvaluation(cell, (int32_t) avgPx, (int32_t) avgPy, oldCost, newCost, costFunction);
  }  // end if

    // if(!moveCell(cell, avgPx_1,avgPy_1)) {
    //   std::cout << "[WARNING]: move error at " << __FILE__ << ": " << __LINE__ << "\n";
    // }else{
    //   success = true;
    // }




  return success;
}

// utility
bool QuadraticTDP::canBeSetAsMovable(ContestInstance* cell, const bool considerCriticalCellsAsFixed)
{
  return !cell->isFixed() && !cell->isFlipflop() && !cell->isBuffer() && !cell->isMacro()
         && !(considerCriticalCellsAsFixed && (getCellCriticality(cell, Mode::LATE) > 0));
}  // end method

void QuadraticTDP::removeAnchors()
{
  fw.clear();
  fx.clear();
  fy.clear();
  fw.assign(mapIndexToCell.size(), 0);
  fx.assign(mapIndexToCell.size(), 0);
  fy.assign(mapIndexToCell.size(), 0);
}

double QuadraticTDP::getNetCriticality(ContestNet* net)
{
  double net_criticality = 0;
  for (auto pin : net->get_pins()) {
    net_criticality = std::max(getPinCriticality(pin), net_criticality);  // 待办
  }

  return net_criticality;
}

double QuadraticTDP::getSmoothedCriticality(ContestPin* pin)
{
  const double pinCriticality = getPinCriticality(pin);
  if (pinCriticality < 1e-6)
    return 0.0f;
  else if (approximatelyEqual(pinCriticality, medianCriticality))
    return 0.5f;
  else if (pinCriticality > medianCriticality)
    return 0.5f * (1.0f + std::sqrt((pinCriticality - medianCriticality) / (1 - medianCriticality)));
  else
    return 0.5f * (1.0f - std::sqrt((medianCriticality - pinCriticality) / (medianCriticality)));
}

double QuadraticTDP::getPinCriticality(ContestPin* pin)
{
  double nslack = std::min(pin->get_late_slack(), 0.0);

  return wns < 0 ? std::max((double) 0, (double)(nslack / wns)) : 0;
}

double QuadraticTDP::getPinCentrality(ContestPin* pin)
{
  return 0.5;
  // double centrality = pin->get_centrality() / _maxCentrality;
  // return centrality;
}

double QuadraticTDP::getCellWorstSlack(ContestInstance* instance)
{
  double worst_slack = 1000;

  for (auto pin : instance->get_pin_vec()) {
    worst_slack = std::min(worst_slack, pin->get_late_slack());
  }
  return worst_slack;
}

double QuadraticTDP::getCellWorstSlack1(ContestInstance* instance)
{
  double worst_slack = 1000;

  for (auto pin : instance->get_pin_vec()) {
    auto pin_slack = pin2slack_map[pin];
    worst_slack =  pin_slack < worst_slack ? pin_slack : worst_slack;
  }
  return worst_slack;
}

double QuadraticTDP::findPinSlack(ContestPin* pin)
{
  double slack = pin2slack_map[pin];
  return slack;
}


double QuadraticTDP::getCellCriticality(ContestInstance* cell, Mode timing_mode)
{
  double criticality = 0;
  for (auto pin : cell->get_outpin_vec()) {
    criticality = std::max(criticality, getPinCriticality(pin));
  }  // end for
  if (cell->isFlipflop()) {
    for (auto pin : cell->get_pin_vec()) {
      std::string pin_name = pin->get_name();
      std::string port_name = pin_name.substr(pin_name.length() - 1, pin_name.length());
      if (port_name == "D") 
          criticality = std::max(criticality, getPinCriticality(pin));
      }
  }
  return criticality;
}

double QuadraticTDP::getPinEarlyCriticality(ContestPin* pin)
{
  double nslack = std::min(pin->get_early_slack(), 0.0);
  return wns_early < 0 ? std::max((double) 0, std::min((double) 1, nslack / wns_early)) : 0;
}


bool QuadraticTDP::checkMaxDisplacementViolation(const std::string& errorMsg, const bool hideMessageIfPass)
{
  if (!_EnableMaxDisplacementConstraint)
    return true;

  const int maxViolatorsToReport = 10;

  vector<ContestInstance*> violators;
  violators.reserve(maxViolatorsToReport);

  bool moreViolators = false;
  for (auto cell : _contest_database->get_ContestInstance_pvec()) {
    if (violateMaxDisplacement(cell)) {
      if (violators.size() >= maxViolatorsToReport) {
        moreViolators = true;
        break;
      } else {
        violators.push_back(cell);
      }  // end if
    }    // end if
  }      // end for

  const bool pass = violators.empty();
  if (!pass || !hideMessageIfPass) {
    std::cout << "[" << (violators.size() > 0 ? "FAIL" : "PASS") << "] ";
    std::cout << "Max displacement violation checking" << (errorMsg == "" ? "." : (" @ " + errorMsg)) << "\n";

    for (unsigned i = 0; i < violators.size(); i++) {
      ContestInstance* cell = violators[i];
      Point<int32_t> posCell = cell->get_center_coord();
      Point<int32_t> initial = cell->get_anchor_center_point();
      const double ox = initial.get_x();
      const double oy = initial.get_y();
      const double x = posCell.get_x();
      const double y = posCell.get_y();

      const double displacement = computeManhattanDistance(posCell, initial);

      // std::cout << "\t";
      // std::cout << cell.getName() << " "
      // 		<< "ox=" << ox << " "
      // 		<< "oy=" << oy << " "
      // 		<< "x=" << x << " "
      // 		<< "y=" << y << " "
      // 		<< "displacement=" << displacement << " "
      // 		<< "(" << getMaxDisplacement() << ")\n";
    }  // end for

    if (moreViolators) {
      std::cout << "\t";
      std::cout << "At least one more violator... Stopping here.\n";
    }  // end if
  }    // end if

  return violators.size() == 0;
}

void QuadraticTDP::obtainTopCriticalEndpoints(vector<ContestPin*>& most_critical_endpoints, int endpoint_nums)
{
  std::map<double, ContestPin*> endpoint2slack_map;

  for (auto endpoint : _timing_endpoints) {
    endpoint2slack_map[endpoint->get_late_slack()] = endpoint;
  }
  if (!endpoint2slack_map.empty()) {
    int count = 0;
    for (auto it = endpoint2slack_map.begin(); it != endpoint2slack_map.end(); it--) {
      count++;
      most_critical_endpoints.push_back(it->second);
      if (count == endpoint_nums)
        break;
    }
  }

  for(auto &pin : most_critical_endpoints)
  {
      std::cout<<"pin slack: " << pin->get_late_slack()<<std::endl;
  }


}

double QuadraticTDP::computePathManhattanLength(const std::vector<ContestPin*>& path)
{
  double length = 0.0;
  const int numPins = path.size();

  for (auto it = path.begin(); it != path.end(); it++) {
    auto currPin = *it;
    it++;
    if (it == path.end())
      break;
    auto nextPin = *it;
    const auto currCell = currPin->get_ContestInstance();
    const auto nextCell = nextPin->get_ContestInstance();
    if (currCell == nextCell)
      continue;
    if (currPin->get_ContestNet()->isClockNet() || currCell->isBuffer())
      continue;

    const auto currPos = currPin->get_center_coord();
    const auto nextPos = nextPin->get_center_coord();

    length += computeManhattanDistance(currPos, nextPos);
  }  // end for

  return length;

}  // end method

bool QuadraticTDP::moveCellWithCostEvaluation(ContestInstance* cell, const int32_t x, const int32_t y, double& oldCost, double& newCost,
                                              CostType costFunction)
{
  oldCost = computeCost(cell, costFunction);
  bool success = moveCellWithCostEvaluationCached(cell, x, y, costFunction, oldCost, newCost);
  return success;
}  // end method

double QuadraticTDP::computeManhattanDistance(Point<int32_t> driverPos, Point<int32_t> sinkPos)
{
  return std::abs(driverPos.get_x() - sinkPos.get_x()) + std::abs(driverPos.get_y() - sinkPos.get_y());
}

double QuadraticTDP::getPinImportance(ContestPin* pin)
{
  return (2 * getPinCentrality(pin) + getPinCriticality(pin)) / 3;
}  // end method

bool QuadraticTDP::violateMaxDisplacement(ContestInstance* cell)
{
  if (_EnableMaxDisplacementConstraint) {
    if (cell->isFixed() || cell->isMacro())
      return false;

    const double displacement = computeManhattanDistance(cell->get_center_coord(), cell->get_initial_pos());
    return displacement > (double) getMaxDisplacement();
  } else {
    return false;
  }
}

bool QuadraticTDP::translateCellWithCostEvaluation(ContestInstance* cell, const int32_t dx, const int32_t dy, double& oldCost, double& newCost)
{
  Point<int32_t> cellPos = cell->get_center_coord();
  const int32_t x = cellPos.get_x();
  const int32_t y = cellPos.get_y();

  bool success = moveCellWithCostEvaluationCached(cell, x + dx, y + dy, CostType::COST_LOCAL_DELAY, oldCost, newCost);
  return success;
}  // end method

double QuadraticTDP::computeCost(ContestInstance* cell, const CostType costFunction)
{
  switch (costFunction) {
    case COST_NONE:
      return 0;
    case COST_WIRELENGTH:
      return computeCost_Wirelength(cell);
    case COST_RC:
      return computeCost_RC(cell);
    case COST_LOCAL_DELAY:
      return computeCost_LocalDelay(cell);
    default:
      assert(false);
      return 0;
  }  // end switch
}  // end method

double QuadraticTDP::computeCost_LocalDelay(ContestInstance* cell)
{
  double cost = 0;

  // [NOTE] After a local timing update, criticalities may change. I think
  // the most appropriate approach would be to store the current
  // criticalities and keep them as constants.

  // Get the wire delay at all local sink pins (side cells and sink cells).
  for (auto pin : cell->get_pin_vec()) {
    auto net = pin->get_ContestNet();
    if (net) {
      for (auto sink : net->get_sink_pins()) {
        if (sink->get_ContestInstance() == cell)
          continue;

        cost += getPinImportance(sink) * sink->get_arrival_late_time();
      }  // end for
    }    // end if
  }      // end for

  return cost;
}  // end method

double QuadraticTDP::computeCost_Wirelength(ContestInstance* cell)
{
  double cost = 0;

  for (auto pin : cell->get_pin_vec()) {
    auto net = pin->get_ContestNet();
    if (net) {
      const double criticality = getNetCriticality(net);
      // TODO：
      //  cost += criticality * getNetWirelength(net);//
    }  // end if
  }    // end for

  return cost;
}
double QuadraticTDP::computeCost_RC(ContestInstance* cell)
{
}

bool QuadraticTDP::moveCellWithCostEvaluationCached(ContestInstance* cell, const int32_t x, const int32_t y, const CostType costFunction,
                                                    const double oldCost, double& newCost)
{
  const Point<int32_t> cellPos = cell->get_center_coord();
  const int32_t oldx = cellPos.get_x();
  const int32_t oldy = cellPos.get_y();

  // Try to move the cell.
  const bool success = moveCell(cell, x, y);
  return success;
}  // end method

bool QuadraticTDP::moveCell(ContestInstance* cell, const double x, const double y)
{
  if (cell->isFixed()) {
    LOG_WARNING << "\n[BUG] Moving a cell which is fixed in the input file. Skipping...\n";
    return false;
  }  // end if


  const int32_t preivousX = cell->get_lower_point().get_x();
  const int32_t preivousY = cell->get_lower_point().get_y();

  // Get actual target x, y that do not violate max displacement rule.
  int32_t boundedx;
  int32_t boundedy;
  if (_EnableMaxDisplacementConstraint) {
    computeBoundedPosition(cell, x, y, boundedx, boundedy);
  } else {
    boundedx = x;
    boundedy = y;
  }  // end else

  // Update cell position to the target location.
  const bool success = placeCell(cell, boundedx, boundedy);
  if (success) {
  //  auto idb_cell = _contest_database->get_Idbinstace_map()[cell];
  //  idb_cell->set_coodinate(cell->get_lower_point().get_x(), cell->get_lower_point().get_y());
    LOG_INFO << "cell move has succeed ! ! !";
  } else {
    LOG_WARNING << "cell move doesn't succeed ! ! !";
  }
  return success;
}

void QuadraticTDP::computeCost_UpdateAfterMove(ContestInstance* cell, const CostType costFunction)
{
}

double QuadraticTDP::getPinResistance(ContestPin* driver)
{
  // auto* timing_engine = ista::TimingEngine::getOrCreateTimingEngine();
  auto driver_name = driver->get_name();
  auto* sta_vertex = _contest_database->get_timing_engine()->findVertex(driver_name.c_str());
  auto* pin_obj = sta_vertex->get_design_obj();
  ista::Pin* pin = dynamic_cast<ista::Pin*>(pin_obj);  // 可以将 指向基类的指针转向派生类
  ista::LibertyPort* lib_port = pin->get_cell_port();
  double driver_resistance = lib_port->driveResistance();
  return driver_resistance;
}

double QuadraticTDP::getPinCap(ContestPin* pin)
{
  
  auto driver_name = pin->get_name();
  auto* sta_vertex = _contest_database->get_timing_engine()->findVertex(driver_name.c_str());
  auto* pin_obj = sta_vertex->get_design_obj();
  ista::Pin* pin_ptr = dynamic_cast<ista::Pin*>(pin_obj);  // 可以将 指向基类的指针转向派生类
  ista::LibertyPort* lib_port = pin_ptr->get_cell_port();
  double pin_cap = lib_port->get_port_cap();
  return pin_cap;
}


void QuadraticTDP::obtainOnePathPin(ContestPin* endpoint, std::vector<ContestPin*>& need_fix_instances)
{
  std::queue<ContestPin*> que;
  que.push(endpoint);
  need_fix_instances.push_back(endpoint);
  while (true) {
    double min_driver_pin_slack = DBL_MAX;
    ContestPin* most_critical_inpin = nullptr;
    auto it = que.front();
    que.pop();
    auto net = it->get_ContestNet();
    auto driver_pin = net->get_driver_pin();
    need_fix_instances.push_back(driver_pin);
    auto iter = std::find(_timing_startpoints.begin(), _timing_startpoints.end(), driver_pin);
    if (iter != _timing_startpoints.end()) {
      break;
    } else {
      auto driver_instance = driver_pin->get_ContestInstance();
      for (auto pin : driver_instance->get_inpin_vec()) {
        if (min_driver_pin_slack > pin->get_late_slack()) {
          min_driver_pin_slack = pin->get_late_slack();
          most_critical_inpin = pin;
        }
      }

      need_fix_instances.push_back(most_critical_inpin);
      que.push(most_critical_inpin);
    }
  }
}

void QuadraticTDP::computeBoundedPosition(ContestInstance* cell, const int32_t x, const int32_t y, int32_t& boundedx, int32_t& boundedy)
{
  // Defensive programming. To avoid any max displacement violation due
  // to rounding errors, let's reduce the max displacement by the site
  // width.
  const int32_t maxDisplacement = getMaxDisplacement();
  const Point<int32_t> initCellPos = cell->get_center_coord();
  const int32_t ox = initCellPos.get_x();
  const int32_t oy = initCellPos.get_y();

  const int32_t dx = x - ox;
  const int32_t dy = y - oy;
  const int32_t d = std::abs(dx) + std::abs(dy);

  const double ratio = maxDisplacement / double(d);
  if (ratio < 1) {
    boundedx = (int32_t) (ox + ratio * dx);
    boundedy = (int32_t) (oy + ratio * dy);
  } else {
    boundedx = x;
    boundedy = y;
  }  // end else
}  // end method

bool QuadraticTDP::placeCell(ContestInstance* cell, const int32_t x, const int32_t y)
{
  bool success;
  const bool need_moved = (x != cell->get_center_coord().get_x()) || (y != cell->get_center_coord().get_y());

  if (need_moved) {
    cell->set_center_point(Point<int32_t>(x, y));
    // auto width = cell->get_width();
    // auto height = cell->get_height();
    // cell->set_lower_point(Point<int32_t>(x - (width/2), y - + (height/2)));
    // cell->
    // cell->set_center_point(Point<int32_t>(x + (width/2), y + (height/2)));
    success = true;
  }
  return success;
}

void QuadraticTDP::obtainEndpoints()
{
  for (auto pin : _contest_database->get_ContestPin_pvec()) {
    bool flipflop_input_flag = false;
    bool flipflop_output_flag = false;

    auto inst = pin->get_ContestInstance();
    if (inst && inst->isFlipflop()) {
      if (isFlipflopDataInput(pin)) {
        flipflop_input_flag = true;
      }
      if (pin->isInstanceOutputPin()) {
        flipflop_output_flag = true;
      }
    }

    if (pin->isPO() || flipflop_input_flag) {
      _timing_endpoints.emplace(pin);
    }
    if (pin->isPI() || pin->isClockPin() || flipflop_output_flag) {
      _timing_startpoints.emplace(pin);
    }
  }
}

void QuadraticTDP::buildNetTopo()
{
  int topo_id = 0;
  std::queue<ContestNet*> net_queue;
  // init
  for (auto net : _contest_database->get_ContestNet_pvec()) {
    net->set_traversed(false);
  }

  // traverse
  for (auto endpoint : _timing_endpoints) {
    net_queue.push(endpoint->get_ContestNet());
  }
  while (!net_queue.empty()) {
    auto cur_net = net_queue.front();
    net_queue.pop();
    _net_to_topo_id.emplace(cur_net, topo_id);
    _topo_id_to_net.emplace(topo_id, cur_net);
    topo_id++;
    cur_net->set_traversed(true);
    auto driver_pin = cur_net->get_driver_pin();
    auto it = _timing_startpoints.find(driver_pin);
    if (it != _timing_startpoints.end()) {
      continue;
    }
    auto driver = driver_pin->get_ContestInstance();
    if (!driver) {
      continue;
    }
    for (auto inpin : driver->get_inpin_vec()) {
      auto inpin_net = inpin->get_ContestNet();
      if (inpin_net->get_traversed() || !inpin_net) {
        continue;
      } else {
        net_queue.push(inpin_net);
      }
    }
  }
}

bool QuadraticTDP::isFlipflopDataInput(ContestPin* pin)
{
  auto inst = pin->get_ContestInstance();
  if (!inst) {
    // 待办
    LOG_ERROR << pin->get_name() << "+ not belong to a flipflop";
    return false;
  }
  if (!inst->isFlipflop()) {
    // 待办
    LOG_ERROR << pin->get_name() << "+ not belong to a flipflop";
    return false;
  }

  std::string pin_name = pin->get_name();
  std::string port_name = pin_name.substr(pin_name.length() - 1, pin_name.length());
  if (port_name == "D") {
    return true;
  } else {
    return false;
  }
}


// 待办！！
void QuadraticTDP::updateTiming_Centrality_Net(ContestNet* net)
{
  // Update the centrality of this sink.
  if (net->get_traversed())
    return;
  net->set_traversed(true);
  int net_centralities = net->get_centrality();
  for (auto* sink : net->get_sink_pins()) {
    net_centralities += sink->get_centrality();
  }
  net->set_centrality(net_centralities);
#ifdef DEBUG
  std::cout << "net name : " << net->get_name() << " net centrality : " << net->get_centrality() << std::endl;
#endif

  auto driver_pin = net->get_driver_pin();
  auto it = _timing_startpoints.find(driver_pin);
  if (it != _timing_startpoints.end()) {
    return;
  }
  auto driver = driver_pin->get_ContestInstance();
  if (!driver || driver->isFlipflop()) {
    return;
  }
  ContestPin* most_critical_inpin = nullptr;
  double most_slack = DBL_MAX;
  for (auto* driver_inpin : driver->get_inpin_vec()) {
    if (!driver_inpin)
      continue;
    if (driver_inpin->get_late_slack() <= most_slack) {
      most_slack = driver_inpin->get_late_slack();
      most_critical_inpin = driver_inpin;
    }
  }
  if (most_critical_inpin) {
    most_critical_inpin->set_centrality(net->get_centrality());
  }
#ifdef DEBUG
  std::cout << "most_critical_inpin name : " << most_critical_inpin->get_name()
            << " most_critical_inpin centrality : " << most_critical_inpin->get_centrality() << std::endl;
#endif
}
void QuadraticTDP::updateTimingCentrality()
{
  buildNetTopo();
  for (auto net : _contest_database->get_ContestNet_pvec()) {
    net->set_traversed(false);
    for (auto pin : net->get_sink_pins()) {
      pin->set_centrality(0.0);
    }
    net->set_centrality(0.0);
  }

  for (auto endpoint : _timing_endpoints) {
    if (endpoint->get_late_slack() < 0) {
      endpoint->set_centrality(1.0);
    } else {
      endpoint->set_centrality(0.0);
    }
  }
#ifdef DEBUG
  for (auto endpoint : _timing_endpoints) {
    std::cout << "endpoint name : " << endpoint->get_name() << " endpoint lateslack : " << endpoint->get_late_slack() << std::endl;
  }
#endif

  for (auto it = _topo_id_to_net.begin(); it != _topo_id_to_net.end(); it++) {
    auto net = it->second;
    updateTiming_Centrality_Net(net);
  }

#ifdef DEBUG
  for (auto pin : _contest_database->get_ContestPin_pvec()) {
    std::cout << "pin name : " << pin->get_name() << " pin centrality : " << pin->get_centrality() << std::endl;
  }
#endif

  for (auto net : _contest_database->get_ContestNet_pvec()) {
    _maxCentrality = std::max(net->get_centrality(), _maxCentrality);
  }
}
// void QuadraticTDP::printCentrality()
// {
//   _contest_database->get_timing_engine()->updateTiming(); 
//   updateTimingCentrality();
//   for (auto pin : _contest_database->get_ContestPin_pvec()) {
//     if (!pin->isInstanceInputPin())
//       continue;
//     double centrality = getPinCentrality(pin);
//     LOG_INFO << "pin name : " << pin->get_name() << " centrality : " << centrality;
//   }
// }

bool QuadraticTDP::approximatelyEqual(const double a, const double b, const double precision)
{
  return std::abs(a - b) <= ((std::abs(a) < std::abs(b) ? std::abs(b) : std::abs(a)) * precision);
}  // end method

template <typename T>
bool definitelyGreaterThan(const T a, const T b, const T precision = 1e-6f)
{
  return (a - b) > ((std::abs(a) < std::abs(b) ? std::abs(b) : std::abs(a)) * precision);
}  // end method

}  // namespace ieda_contest
